// LeetCode 主站 Problem Nr. 111: 二叉树的最小深度

/*
给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：
	输入：root = [3,9,20,null,null,15,7]
	输出：2
示例 2：
	输入：root = [2,null,3,null,4,null,5,null,6]
	输出：5

提示：
	树中节点数的范围在 [0, 105] 内
	-1000 <= Node.val <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

package main

import "github.com/saint-yellow/think-leetcode/ds"

type TreeNode = ds.BinaryNode[int]

func minDepth(root *TreeNode) int {
	return method1(root)
}

// 基于DFS的解法
func method1(root *TreeNode) int {
	if root == nil {
		return 0
	}

	leftDepth := method1(root.Left)
	rightDepth := method1(root.Right)

	if leftDepth != 0 && rightDepth != 0 {
		return 1 + min(leftDepth, rightDepth)
	} else if leftDepth == 0 {
		return 1 + rightDepth
	} else {
		return 1 + leftDepth
	}

}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

// 基于BFS的解法
func method2(root *TreeNode) int {
	queue := []*TreeNode{}
	depths := []int{}

	if root != nil {
		queue = append(queue, root)
		depths = append(depths, 1)
	}

	for i := 0; i < len(queue); i++ {
		node := queue[i]
		depth := depths[i]

		if node.Left == nil && node.Right == nil {
			return depth
		}

		if node.Left != nil {
			queue = append(queue, node.Left)
			depths = append(depths, depth+1)
		}

		if node.Right != nil {
			queue = append(queue, node.Right)
			depths = append(depths, depth+1)
		}

	}

	return 0
}